/*
 * Copyright (C) 2008 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.android.dx.dex.code;

import java.util.ArrayList;
import java.util.HashSet;

import com.android.dx.rop.code.BasicBlock;
import com.android.dx.rop.code.BasicBlockList;
import com.android.dx.rop.code.RopMethod;
import com.android.dx.rop.cst.CstType;
import com.android.dx.rop.type.Type;
import com.android.dx.rop.type.TypeList;
import com.android.dx.util.IntList;

/**
 * Constructor of {@link CatchTable} instances from {@link RopMethod} and
 * associated data.
 */
public final class StdCatchBuilder implements CatchBuilder {

	/** the maximum range of a single catch handler, in code units */
	private static final int MAX_CATCH_RANGE = 65535;

	/** {@code non-null;} method to build the list for */
	private final RopMethod method;

	/** {@code non-null;} block output order */
	private final int[] order;

	/** {@code non-null;} address objects for each block */
	private final BlockAddresses addresses;

	/**
	 * Constructs an instance. It merely holds onto its parameters for a
	 * subsequent call to {@link #build}.
	 * 
	 * @param method
	 *            {@code non-null;} method to build the list for
	 * @param order
	 *            {@code non-null;} block output order
	 * @param addresses
	 *            {@code non-null;} address objects for each block
	 */
	public StdCatchBuilder(RopMethod method, int[] order,
			BlockAddresses addresses) {
		if (method == null) {
			throw new NullPointerException("method == null");
		}

		if (order == null) {
			throw new NullPointerException("order == null");
		}

		if (addresses == null) {
			throw new NullPointerException("addresses == null");
		}

		this.method = method;
		this.order = order;
		this.addresses = addresses;
	}

	/** {@inheritDoc} */
	public CatchTable build() {
		return build(method, order, addresses);
	}

	/** {@inheritDoc} */
	public boolean hasAnyCatches() {
		BasicBlockList blocks = method.getBlocks();
		int size = blocks.size();

		for (int i = 0; i < size; i++) {
			BasicBlock block = blocks.get(i);
			TypeList catches = block.getLastInsn().getCatches();
			if (catches.size() != 0) {
				return true;
			}
		}

		return false;
	}

	/** {@inheritDoc} */
	public HashSet<Type> getCatchTypes() {
		HashSet<Type> result = new HashSet<Type>(20);
		BasicBlockList blocks = method.getBlocks();
		int size = blocks.size();

		for (int i = 0; i < size; i++) {
			BasicBlock block = blocks.get(i);
			TypeList catches = block.getLastInsn().getCatches();
			int catchSize = catches.size();

			for (int j = 0; j < catchSize; j++) {
				result.add(catches.getType(j));
			}
		}

		return result;
	}

	/**
	 * Builds and returns the catch table for a given method.
	 * 
	 * @param method
	 *            {@code non-null;} method to build the list for
	 * @param order
	 *            {@code non-null;} block output order
	 * @param addresses
	 *            {@code non-null;} address objects for each block
	 * @return {@code non-null;} the constructed table
	 */
	public static CatchTable build(RopMethod method, int[] order,
			BlockAddresses addresses) {
		int len = order.length;
		BasicBlockList blocks = method.getBlocks();
		ArrayList<CatchTable.Entry> resultList = new ArrayList<CatchTable.Entry>(
				len);
		CatchHandlerList currentHandlers = CatchHandlerList.EMPTY;
		BasicBlock currentStartBlock = null;
		BasicBlock currentEndBlock = null;

		for (int i = 0; i < len; i++) {
			BasicBlock block = blocks.labelToBlock(order[i]);

			if (!block.canThrow()) {
				/*
				 * There is no need to concern ourselves with the placement of
				 * blocks that can't throw with respect to the blocks that *can*
				 * throw.
				 */
				continue;
			}

			CatchHandlerList handlers = handlersFor(block, addresses);

			if (currentHandlers.size() == 0) {
				// This is the start of a new catch range.
				currentStartBlock = block;
				currentEndBlock = block;
				currentHandlers = handlers;
				continue;
			}

			if (currentHandlers.equals(handlers)
					&& rangeIsValid(currentStartBlock, block, addresses)) {
				/*
				 * The block we are looking at now has the same handlers as the
				 * block that started the currently open catch range, and adding
				 * it to the currently open range won't cause it to be too long.
				 */
				currentEndBlock = block;
				continue;
			}

			/*
			 * The block we are looking at now has incompatible handlers, so we
			 * need to finish off the last entry and start a new one. Note: We
			 * only emit an entry if it has associated handlers.
			 */
			if (currentHandlers.size() != 0) {
				CatchTable.Entry entry = makeEntry(currentStartBlock,
						currentEndBlock, currentHandlers, addresses);
				resultList.add(entry);
			}

			currentStartBlock = block;
			currentEndBlock = block;
			currentHandlers = handlers;
		}

		if (currentHandlers.size() != 0) {
			// Emit an entry for the range that was left hanging.
			CatchTable.Entry entry = makeEntry(currentStartBlock,
					currentEndBlock, currentHandlers, addresses);
			resultList.add(entry);
		}

		// Construct the final result.

		int resultSz = resultList.size();

		if (resultSz == 0) {
			return CatchTable.EMPTY;
		}

		CatchTable result = new CatchTable(resultSz);

		for (int i = 0; i < resultSz; i++) {
			result.set(i, resultList.get(i));
		}

		result.setImmutable();
		return result;
	}

	/**
	 * Makes the {@link CatchHandlerList} for the given basic block.
	 * 
	 * @param block
	 *            {@code non-null;} block to get entries for
	 * @param addresses
	 *            {@code non-null;} address objects for each block
	 * @return {@code non-null;} array of entries
	 */
	private static CatchHandlerList handlersFor(BasicBlock block,
			BlockAddresses addresses) {
		IntList successors = block.getSuccessors();
		int succSize = successors.size();
		int primary = block.getPrimarySuccessor();
		TypeList catches = block.getLastInsn().getCatches();
		int catchSize = catches.size();

		if (catchSize == 0) {
			return CatchHandlerList.EMPTY;
		}

		if (((primary == -1) && (succSize != catchSize))
				|| ((primary != -1) && ((succSize != (catchSize + 1)) || (primary != successors
						.get(catchSize))))) {
			/*
			 * Blocks that throw are supposed to list their primary successor --
			 * if any -- last in the successors list, but that constraint
			 * appears to be violated here.
			 */
			throw new RuntimeException(
					"shouldn't happen: weird successors list");
		}

		/*
		 * Reduce the effective catchSize if we spot a catch-all that isn't at
		 * the end.
		 */
		for (int i = 0; i < catchSize; i++) {
			Type type = catches.getType(i);
			if (type.equals(Type.OBJECT)) {
				catchSize = i + 1;
				break;
			}
		}

		CatchHandlerList result = new CatchHandlerList(catchSize);

		for (int i = 0; i < catchSize; i++) {
			CstType oneType = new CstType(catches.getType(i));
			CodeAddress oneHandler = addresses.getStart(successors.get(i));
			result.set(i, oneType, oneHandler.getAddress());
		}

		result.setImmutable();
		return result;
	}

	/**
	 * Makes a {@link CatchTable#Entry} for the given block range and handlers.
	 * 
	 * @param start
	 *            {@code non-null;} the start block for the range (inclusive)
	 * @param end
	 *            {@code non-null;} the start block for the range (also
	 *            inclusive)
	 * @param handlers
	 *            {@code non-null;} the handlers for the range
	 * @param addresses
	 *            {@code non-null;} address objects for each block
	 */
	private static CatchTable.Entry makeEntry(BasicBlock start, BasicBlock end,
			CatchHandlerList handlers, BlockAddresses addresses) {
		/*
		 * We start at the *last* instruction of the start block, since that's
		 * the instruction that can throw...
		 */
		CodeAddress startAddress = addresses.getLast(start);

		// ...And we end *after* the last instruction of the end block.
		CodeAddress endAddress = addresses.getEnd(end);

		return new CatchTable.Entry(startAddress.getAddress(),
				endAddress.getAddress(), handlers);
	}

	/**
	 * Gets whether the address range for the given two blocks is valid for a
	 * catch handler. This is true as long as the covered range is under 65536
	 * code units.
	 * 
	 * @param start
	 *            {@code non-null;} the start block for the range (inclusive)
	 * @param end
	 *            {@code non-null;} the start block for the range (also
	 *            inclusive)
	 * @param addresses
	 *            {@code non-null;} address objects for each block
	 * @return {@code true} if the range is valid as a catch range
	 */
	private static boolean rangeIsValid(BasicBlock start, BasicBlock end,
			BlockAddresses addresses) {
		if (start == null) {
			throw new NullPointerException("start == null");
		}

		if (end == null) {
			throw new NullPointerException("end == null");
		}

		// See above about selection of instructions.
		int startAddress = addresses.getLast(start).getAddress();
		int endAddress = addresses.getEnd(end).getAddress();

		return (endAddress - startAddress) <= MAX_CATCH_RANGE;
	}
}
